package ljl.alg.wangzheng_camp.round1.find_the_law;

import java.util.ArrayList;
import java.util.List;

public class _54_spiral_order {
    
    /**
     * 做了几亿次了
     * 还是错了，可惜可惜
     * */
    public List<Integer> spiralOrder2(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        if (matrix.length == 0) return res;
        int m = matrix.length, n = matrix[0].length;
        int top = 0, left = 0, bottom = m - 1, right = n - 1;
        while (top <= bottom && left <= right) {
            // 先往右看看
            for (int i = 0; i <= right ; i++) {
                res.add(matrix[top][i]);
            }
            // 往下看看
            for (int i = top + 1; i <= bottom; i++) {
                res.add(matrix[i][right]);
            }
            // 想往左走，条件是：bottom 必须比 top 大，不然重复了
            if (bottom > top) {
                // 往左
                for (int i = right - 1; i >= left ; i--) {
                    res.add(matrix[bottom][i]);
                }
            }
            // 这个条件被我忽略了
            // 想往上走，必须左右不挨着，不然重复
            if (left < right)
                // 往上
                for (int i = bottom - 1; i > top ; i--) {
                    res.add(matrix[i][left]);
                }
           
            left++; right--; top++; bottom--;
        }
        return res;
    }
    
    /**
     * 这次试试带方向盘的
     * 这种解法也挺有意思的
     *
     * 有时我就想，人可以把代码写成垃圾到什么地步
     *
     * */
    public List<Integer> spiralOrder_laji(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int m = matrix.length, n = matrix[0].length;
        boolean[][] visited = new boolean[m][n];
        int i = 0;
        int total = m * n;
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int dirIndex = 0;
        int x = 0, y = 0;
        res.add(matrix[x][y]);
        visited[0][0] = true;
        while (++i < total) {
            int[] dir = dirs[dirIndex % 4];
            int newX = x + dir[0], newY = y + dir[1];
            if (newX < 0 || newY < 0 || newX >= m || newY >= n || visited[newX][newY]) {
                dir = dirs[++dirIndex % 4];
                newX = x + dir[0];
                newY = y + dir[1];
            }
            x = newX;
            y = newY;
            visited[x][y] = true;
            res.add(matrix[x][y]);
        }
        return res;
    }
    
    public List<Integer> spiralOrder333(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int m = matrix.length, n = matrix[0].length;
        boolean[][] visited = new boolean[m][n];
        int i = 0;
        int total = m * n;
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int dirIndex = 0;
        int x = 0, y = 0;
        while (i++ < total) {
            res.add(matrix[x][y]);
            visited[x][y] = true;
            int[] dir = dirs[dirIndex % 4];
            int newX = x + dir[0], newY = y + dir[1];
            if (newX < 0 || newY < 0 || newX >= m || newY >= n || visited[newX][newY]) {
                dir = dirs[++dirIndex % 4];
                newX = x + dir[0];
                newY = y + dir[1];
            }
            x = newX; y = newY;
        }
        return res;
    }
    
    /**
     * 精简版
     * */
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        int m = matrix.length, n = matrix[0].length;
        boolean[][] visited = new boolean[m][n];
        int i = 0;
        int total = m * n;
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int dirIndex = 0;
        int x = 0, y = 0;
        while (i++ < total) {
            res.add(matrix[x][y]);
            visited[x][y] = true;
            int newX = x + dirs[dirIndex][0], newY = y + dirs[dirIndex][1];
            if (newX < 0 || newY < 0 || newX >= m || newY >= n || visited[newX][newY]) {
                dirIndex = (dirIndex + 1) % 4;
            }
            x += dirs[dirIndex][0]; y += dirs[dirIndex][1];
        }
        return res;
    }
}
